﻿#include <iostream>
using namespace std;

/*
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
*/

 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

 /*错了
 class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode* superior = dummyHead;

        // 1. 遍历至m的前一个节点
        while (m > 1) {
            superior = superior->next;
            m--;
        }
        ListNode* pre = NULL;
        ListNode* cur = superior->next;
        int x = n - m+1;
        while (x > 0) {
            ListNode* t = cur->next;
            cur->next = pre;
            pre = cur;
            cur = t;
            x--;
        }
        superior->next->next = cur;
        superior->next = pre;
      

        return dummyHead->next;
    }
};
 */
 class Solution {
 public:
     ListNode* reverseBetween(ListNode* head, int m, int n) {
         int change_len = n - m + 1;
         ListNode* pre_head = NULL;//初始化开始逆置的节点的前驱
         ListNode* result = head;
         while (head && --m)
         {
             pre_head = head;
             head = head->next;
         }
         ListNode* modify_list_tail = head;//逆置后的链表尾
         ListNode* new_head = NULL;
         while (head && change_len)
         {
             ListNode* next = head->next;
             head->next = new_head;
             new_head = head;
             head = next;
             change_len--;
         }
         modify_list_tail->next = head;//连接逆置后的链表尾与逆置段的后一个节点
         if (pre_head)//如果prehead不为空，说明不是从第一个节点开始的
         {
             pre_head->next = new_head;
         }
         else
         {
             result = new_head;
         }
         return result;
     }
 };